/**
 * 括号生成
 *
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 * 示例 1：
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：["()"]
 */

import java.util.List;
import java.util.ArrayList;

/**
 * 回溯, 深搜  题目给的 n 也就是左括号和右括号的个数, 我们其实只要把他们的所有
 * 排列组合全都列举一遍就好了, 咱们怎么列举呢, 对啦, 就是深搜了, 在深搜的过程中
 * 我们要注意, 右括号的数量是不能超过左括号的数量的, 为了方便计算, 我们需要将左
 * 括号和右括号的数量传入函数头, 当两种括号总和等于 n * 2的时候也就是函数出口了
 * 时间复杂度 : O(n!)
 * 空间复杂度 : O(n)
 */

public class Main {

    // 定义全局变量, 我们在写深搜的题目, 最好定义全局变量, 因为这会让我们的后续操作
    // 变得简单很多

    // 记录有效括号的组合
    StringBuffer ret;

    // 记录有效括号的总组合
    List<String> list;

    // 记录括号的数量
    int len;

    public List<String> generateParenthesis(int n) {

        // 初始化
        list = new ArrayList<>();
        ret = new StringBuffer();
        len = n;

        dfs(0, 0);
        return list;
    }

    /**
     * 深搜函数
     *
     * @param left  左括号的个数
     * @param right 右括号的个数
     */
    private void dfs (int left, int right) {

        // 保持左括号的数量大于右括号
        // 剪枝
        if (left < right) {
            return;
        }

        // 函数出口
        if (left + right == len * 2) {
            list.add(ret.toString());
            return;
        }

        // 左括号也不能一直加下去, 当左括号的数量达到题目给的数量时, 就不能在家左括号了
        if (left < len) {

            // 加左括号
            ret.append('(');

            // 深搜
            dfs(++left, right);

            // 回溯
            // 恢复现场
            left--;
            ret.deleteCharAt(ret.length() - 1);
        }

        // 右括号也是和左括号一样的道理
        if (right < len) {
            ret.append(')');
            dfs(left, ++right);
            right--;
            ret.deleteCharAt(ret.length() - 1);
        }
    }
}